﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//暴力法优化的思路，子串不是回文，那么父亲肯定不是回文
public class Solution5
{
    public string LongestPalindrome3(string s)//暴力法优化,动态规划
    {

        if (s.Length < 2)
        {
            return s;
        }
        int maxLen = 1;//一个元素也是回文
        int begin = 0;
        string res = "";
        int strLen = s.Length;
        bool[][] dp = new bool[strLen][];
        for (int i = 0; i < s.Length; i++)
        {
            dp[i] = new bool[strLen];
            dp[i][i] = true;//一个元素肯定是回环

        }
        //两端相同而且字串是回文
        //j不能小于i
        //，j-1不能小于i+1,j不能小于i+2,所有字串长度最少=3
        //长度为2的单独判断一下



        //遍历的顺序一定是先遍历短的
        for (int curLen = 2; curLen <= s.Length; curLen++)
        {

            for (int start = 0; start < s.Length; start++)
            {
                int end = start + curLen - 1;
                if (end >= s.Length)//越界
                {
                    break;

                }


                if (s[start] == s[end])
                {

                    if (curLen == 2)//l
                    {
                        dp[start][end] = true;
                    }
                    else
                    {
                        if (dp[start + 1][end - 1])//子串是回文
                        {
                            dp[start][end] = true;

                        }
                    }

                }
                else
                {
                    dp[start][end] = false;
                }


                if (dp[start][end])
                {
                    if (curLen > maxLen)
                    {
                        maxLen = curLen;
                        begin = start;

                    }
                }
            }


        }
        res = s.Substring(begin, maxLen);
        return res;

    }
    public string LongestPalindrome2(string s)//暴力法，两次循环
    {
        int maxLen = 0;
        string res = "";

        for (int i = 0; i < s.Length; i++)
        {

            for (int j = i; j < s.Length; j++)
            {


                bool isHuiwen = Palindrome(s, i, j);
                if (isHuiwen)
                {

                    int curLen = j - i + 1;
                    if (curLen > maxLen)
                    {
                        maxLen = curLen;
                        res = s.Substring(i, curLen);
                    }

                }

            }


        }
        return res;

    }

    private bool Palindrome(string s, int start, int end)
    {

        while (start < end)
        {
            if (s[start] == s[end])
            {
                start++;
                end--;
            }
            else
            {
                return false;
            }


        }
        return true;

    }


    public string LongestPalindrome(string s)
    {
        int maxLen = 0;
        int begin = 0;

        for (int i = 0; i < s.Length; i++)
        {

            for (int j = 0; j < 2; j++)
            {
                //以这个为最新开始扩散
                int left = i;
                int right = i + j;//两个元素也可能回文
                                  //一个元素必须回文，所以可能从一个元素开始扩散


                while (left >= 0 && right < s.Length)
                {

                    if (s[left] == s[right])
                    {


                        int curLen = right - left + 1;
                        if (curLen > maxLen)
                        {
                            begin = left;
                            maxLen = curLen;

                        }
                        left--;
                        right++;
                    }
                    else
                    {
                        //更新
                        break;

                    }
                }

            }
        }



        return s.Substring(begin, maxLen);

    }
}

class Program5
{
    static void Main5 (string[] args)
    {
        Solution5 solution = new Solution5();
        string s = "babad";


        string res = solution.LongestPalindrome(s);
        Console.WriteLine(res);
    }
}
